#define _CRT_SECURE_NO_WARNINGS 1

#include "graph.hpp"

void test1()
{
	matrix::graph<char, int, INT_MAX, true> g("abcd", 4);
	g.edgeAdd('a', 'b', 9);
	g.edgeAdd('c', 'd', 6);
	g.edgeAdd('b', 'd', 3);
	g.print();
}

void test2()
{
	link_table::graph<char, int, true> g("abcd", 4);
	g.edgeAdd('a', 'c', 1);
	g.edgeAdd('a', 'b', 2);
	g.edgeAdd('a', 'd', 3);
	g.print();
}

void test3()
{
	matrix::graph<char, int, INT_MAX, false> g("abcdef", 6);
	g.edgeAdd('a', 'b', 9);
	g.edgeAdd('c', 'd', 6);
	g.edgeAdd('b', 'd', 3);
	g.edgeAdd('a', 'e', 7);
	g.edgeAdd('b', 'f', 5);
	g.edgeAdd('e', 'b', 13);
	g.edgeAdd('e', 'c', 2);

	//matrix::graph<char, int, INT_MAX, false> kMST;
	//cout << g.KrusKal(kMST) << endl;
	//kMST.print();

	matrix::graph<char, int, INT_MAX, false> pMST;
	cout << g.Prim(pMST, 'a') << endl;
	pMST.print();

	//g.DFS('a');
	//g.BFS('a');
	//g.print();
}

void test4()
{
	const char* str = "syztx";
	matrix::graph<char, int, INT_MAX, true> g(str, strlen(str));
	g.edgeAdd('s', 't', 10);
	g.edgeAdd('s', 'y', 5);
	g.edgeAdd('y', 't', 3);
	g.edgeAdd('y', 'x', 9);
	g.edgeAdd('y', 'z', 2);
	g.edgeAdd('z', 's', 7);
	g.edgeAdd('z', 'x', 6);
	g.edgeAdd('t', 'y', 2);
	g.edgeAdd('t', 'x', 1);
	g.edgeAdd('x', 'z', 4);
	vector<int> dist;
	vector<int> path;
	g.Dijkstra('s', dist, path);
	g.printPath('s', dist, path);
}

int main()
{
	//test1();
	//test2();
	//test3();
	test4();
	return 0;
}